﻿#include<iostream>
using namespace std;
int Part(int a[],int s,int t)	//划分算法
{
    int i = s,j = t;
    int tmp = a[s];
    while (i != j)	  
    {
        while (j > i && a[j] >= tmp)
            j--;    	
        a[i] = a[j];	
        while (i < j && a[i] <= tmp)
            i++;   	
        a[j] = a[i];	
    }
    a[i] = tmp;
    return i;
}
void f(int a[],int ss,int kk)
{
    if (ss < kk) 			
    {
        int i = Part(a,ss,kk);
        f(a,ss,i - 1);	
        f(a,i + 1,kk);	
    }
}

int Search(int a[], int l,int n, int k)//递归算法
{                                 
    int mid;
    int low = l; 
    int high = n;
    if (low <= high)		
    {
        mid = (low + high) / 2;	//求查找区间的中间位置
        if (a[mid] == k)		//找到返回其物理下标mid
            return mid;
        if (a[mid] > k)		
            return Search(a,low,mid - 1,k);
        else			
            return Search(a,mid + 1,high,k);
    }
    else return -1;		//若当前查找区间没有元素时返回-1

}
void print(int s[],int g)
{
    for (int i = 0; i < g; i++)
    {
        cout << s[i] << " ";
    }
    cout << endl;
}
int main()
{
    int ss[10] = { 3,5,8,10,15,16,13,27,29,47 };
    print(ss, 10);
    cout << "排序后：" << endl;
    f(ss,0,9);
    print(ss, 10);
    cout << "如果返回-1则没有该元素" << endl;
    while (1)
    {
        cout << "请输入要查找的元素：";
        int s;
        cin >> s;
        cout << "在第：" << Search(ss,0,9, s) << "个位置" << endl;
    }
}

